|
In computational complexity theory, the linear speedup theorem for Turing machines states that given any real ''c'' > 0 and any Turing machine solving a problem in time f(''n''), there is another machine that solves the same problem in time at most ''c''f(''n'') + ''n'' + 2. == Proof == Here is a sketch proof for the case ''c'' = ½. Suppose the Turing machine M solves the problem in f(''n'') steps and that it has ''k'' tape symbols and ''s'' internal states. Construct a new machine M' with ''k''3 tape symbols, each symbol representing a "chunk" of 3 adjacent symbols in machine M. The tape of machine M' is a compressed representation of the tape of machine M, with cell ''i'' for machine M' representing the chunk of cells 2''i''-1, 2''i'' and 2''i''+1 of machine M (note that these chunks overlap). In one computation step, M' simulates the computation of M until M's head leaves the chunk cells to the left or right (this simulation can be done in a single step because M can be in no more than ''3sk''³ states without leaving the chunk or repeating a state). During this simulation M may accept, in which case M' also accepts, or M may loop, in which case M' does nothing (and so also loops). A final subtlety is that, because the chunks can overlap, they may contain inconsistent symbols on the overlapping parts. In this case, the chunk closest to the current head position is the correct one. When transitioning from one chunk to another, the state of the Turing machine is used to remember the overlapping symbol from the starting chunk temporarily, until it can be copied into the corresponding position of the destination chunk. The construction requires that each computation step in M' corresponds to at least 2 computation steps of M. So M' takes no more than f(''n'')/2 steps, after an initial linear number of steps to convert the input tape into the compressed representation. This proof can be easily generalized to all values of ''c'' > 0 by using greater numbers of adjacent symbols per chunk. A similar technique, known as the "tape compression theorem", allows for a similar constant factor reduction in the space requirements of a Turing machine. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「linear speedup theorem」の詳細全文を読む スポンサード リンク
|